HN
Hacker News • 26일 전
IMP 7
트랜스포머는 본질적으로 간결하다
본 논문은 개념을 표현하는 트랜스포머의 표현력을 '간결성(Succinctness)'이라는 척도로 측정할 것을 제안합니다. 연구진은 트랜스포머가 유한 오토마타나 선형 시제 논리(LTL) 공식 같은 전통적 방식들보다 훨씬 더 적은 용량으로 형식 언어를 표현할 수 있음을 수학적으로 증명했습니다. 그러나 이러한 높은 표현력으로 인해 트랜스포머의 특정 속성을 검증하거나 증명하는 작업은 EXPSPACE-완전(EXPSPACE-complete) 문제로, 계산적으로 매우 다루기 어렵다는 한계도 함께 확인했습니다.
트랜스포머 형식언어 표현력